/**
 * \file main.c++
 * \brief Main file
 * 
 *  This program solves the 3n+1 problem given on the Uva website. The problem id 
 * is 100 
 * 
 * \author Rusty Fausk Augustine Mathew
 * \date 6/9/2009
 */

 /** 
 *  \mainpage
 * This is the main entry point of the program which solves the 3n+1 
 * problem. It can be compiled on G++ with -DTEST to run a set of automated
 * tests that ensure the validity of the code
 */
#include <cassert>  // assert
#include <iostream> // cin, cout, endl, ios_base, istream, ostream

#ifdef ONLINE_JUDGE
    #define NDEBUG
#endif

/**
 * input: don't change after reading
 */
int i;

/**
 * input: don't change after reading
 */
int j;

/**
 * output
 */
int v;

/*
 * cache size
 */
const unsigned int CACHE_SIZE = 100000;

/**
 * eager cache
 */
int cache[CACHE_SIZE] = {0};

/**
 * \param v value to compute
 * \param c cycle length so far
 * uses the cache to determine the cycle length of a given value
 * also populates the cache while running recursively
 * \return cycle length
 */
int compute(unsigned int v, int c = 0) {
	assert(v > 0);
	if (v < CACHE_SIZE) {
		if (cache[v]) {
			return c + cache[v];
		}
	}
	if ((v & 1) == 0) {
		v = v >> 1;
	}
	else {
		v = v + (v >> 1) + 1;
		c = c+1;
	}
	int a = compute(v, c+1);
	if (v < CACHE_SIZE) {
		if (!cache[v]) {
			cache[v] = a - c - 1;
		}
	}
	assert(a > 0);
	return a;
}

/**
 * eager cache computation
 */
void populate_cache () {
	cache[1] = 1;
	cache[2] = 2;
	cache[3] = 8;
	cache[6] = 9;
	cache[7] = 17;
	cache[9] = 20;
	cache[18] = 21;
	cache[25] = 24;
	cache[27] = 112;
	cache[54] = 113;
	cache[73] = 116;
	cache[97] = 119;
	cache[129] = 122;
	cache[171] = 125;
	cache[231] = 128;
	cache[313] = 131;
	cache[327] = 144;
	cache[649] = 145;
	cache[703] = 171;
	cache[871] = 179;
	cache[1161] = 182;
	cache[2223] = 183;
	cache[2463] = 209;
	cache[2919] = 217;
	cache[3711] = 238;
	cache[6171] = 262;
	cache[26623] = 308;
	cache[34239] = 311;
	cache[35497] = 311;
	cache[35655] = 324;
	cache[37503] = 306;
	cache[39935] = 306;
	cache[45127] = 314;
	cache[47329] = 314;
	cache[51359] = 309;
	cache[52527] = 340;
	cache[53246] = 309;
	cache[53247] = 309;
	cache[53483] = 322;
	cache[56095] = 322;
	cache[56255] = 304;
	cache[57115] = 304;
	cache[59903] = 304;
	cache[60169] = 317;
	cache[60975] = 335;
	cache[61999] = 317;
	cache[63105] = 317;
	cache[63387] = 330;
	cache[67691] = 312;
	cache[68187] = 312;
	cache[68478] = 312;
	cache[68479] = 312;
	cache[70335] = 312;
	cache[70994] = 312;
	cache[70995] = 312;
	cache[71310] = 325;
	cache[71311] = 325;
	cache[74791] = 325;
	cache[74793] = 325;
	cache[75006] = 307;
	cache[75007] = 307;
	cache[76153] = 307;
	cache[76711] = 307;
	cache[77031] = 351;
	cache[77039] = 307;
	cache[78463] = 307;
	cache[78791] = 338;
	cache[79131] = 307;
	cache[79870] = 307;
	cache[79871] = 307;
	cache[80225] = 320;
	cache[81159] = 320;
	cache[82411] = 307;
	cache[82665] = 320;
	cache[84143] = 320;
	cache[84383] = 302;
	cache[85673] = 302;
	cache[86175] = 302;
	cache[87087] = 333;
	cache[88059] = 333;
	cache[88135] = 302;
	cache[89023] = 302;
	cache[89119] = 315;
	cache[89263] = 302;
	cache[89855] = 302;
	cache[90254] = 315;
	cache[90255] = 315;
	cache[91305] = 315;
	cache[91463] = 333;
	cache[92713] = 302;
	cache[92999] = 315;
	cache[94658] = 315;
	cache[94659] = 315;
	cache[94959] = 302;
	cache[95081] = 328;
	cache[99067] = 328;
	cache[99721] = 328;
	for (unsigned int x = 1; x < CACHE_SIZE; x++) {
		if (!cache[x]) {
			cache[x] = compute(x);
		}
	}
}

/**
 * \param in stream to read from
 * reads an int into i and j
 * \return true if that succeeds, false otherwise
 */
	bool read (std::istream& in) {
		if (!(in >> i))
			return false;
		in >> j;
		return true;}

		/**
		 * computes the max cycle length in the range [i, j]
		 * and stores the result in v
		 */
		void eval () {
			assert(i>0 && i<=10000000 && j>0 && j<=10000000);
			v = 0;
			int lower, upper;
			if (i <= j) {
				lower = i;
				upper = j;
			}
			else {
				lower = j;
				upper = i;
			}
			assert(lower <= upper);
			for (int k = lower; k <= upper; k++) {
				unsigned long int t = k;
				int cycle = 1;
				while (t != 1) {
					// eager cache optimization
					if (t < CACHE_SIZE) {
						cycle = cycle + cache[t] - 1;
						break;
					}
					if ((t & 1) == 0) {
						// even, divide by 2
						t = t >> 1;
					}
					else {
						// odd, do (3n+1)/2, which is 2 cycles
						t = t + (t >> 1) + 1;
						++cycle;
					}
					++cycle;
				}
				if (cycle > v) {
					v = cycle;
				}
			}
}

/**
 * \param i1 first number
 * \param j1 second number
 * \return the highest cycle length between i and j
 */
int eval(int i1, int j1){
	i = i1;
	j = j1;
	eval();
	return v;
}

/**
 * prints the values of i, j, and v
 */
void print (std::ostream& out) {
    out << i << " " << j << " " << v << std::endl;}

#ifdef TEST
    #include "cppunit/TestSuite.h"      // TestSuite
    #include "cppunit/TextTestRunner.h" // TestRunner
    #include "TestCollatz.h"
#endif // TEST

/**
 * either runs the tests or runs the program
 */
int main () {
    using namespace std;
    ios_base::sync_with_stdio(false);     // turn off synchronization with C I/O

	// eager cache computation
	populate_cache();

    #ifdef TEST
        using namespace CppUnit;
        TextTestRunner tr;
        tr.addTest(TestCollatz::suite());
        tr.run();
    #else
        while (read(cin)) {
            eval();
            print(cout);}
    #endif // TEST

    return 0;}
